Normally, a division process can be described to a succession of subtractions and shifts, in much the same manner that multiplication can be implemented by a series of additions and shifts.
The conventional method of division may be expressed as being a number of formal steps. Manually, the divisor and dividend are compared, the divisor is multiplied by a first quotient digit, and a subtraction is made. Then, the dividend is shifted one place to the left after each subtraction is completed.
Electronically, if the divisor is equal to or less than a dividend, a "1" is entered in the quotient and the divisor is subtracted from the dividend. If the divisor is larger than the dividend, a zero is subtracted and a "0" is entered in the quotient. The process repeats with the modified or partial dividend. The procedure terminates when a correct number of places has been generated in the quotient. Thus, it is necessary to perform may subtractions and left shifts.
A conventional binary division system comprises a register that holds the divisor. A shift register contains the dividend or the partial dividend. The quotient is entered on a one bit-by-bit basis, as clock pulses appear to control a subtractor and a comparator circuit.
It can be expensive to include a special comparator in a division logic system. Consequently, many computers perform the comparison operation by subtracting the divisor from the dividend. The original dividend must be restored by the subsequent addition of the divisor, if the divisor is larger than the dividend, as can be seen from the above description.
This method is called "restoring division." Obviously, it requires a long time to complete a division by this method, as compared to the time required for using the basic technique. To speed up the execution time, a method may be used so that, if a test subtraction gives a negative remainder, it is nullified by adding back half the divisor in the next arithmetic step. This method is called "non-restoring division."
A synchronous division system requires a series of subtractions and shifts, so that it is indispensable to use a fast clock rate circuitry in order to speed up the division system. However, a fast bit shift causes a bit transfer error in the shift registers that often results in an erroneous quotient.
An iterative division using only multiplication had been proposed by Wallace (a suggestion for a fast multiplier is found in the IEEE Transactions; Electronic Computers, 1964, EC 13, 14-17). In this approach, the quotient is generated by multiplying the dividend by the reciprocal of the divisor which is produced by iterative multiplications, starting with an initial guess as to the approximation of the reciprocals. In this approach, the iteration of the multiplication is indispensable. Therefore, there is a slowdown of the division time.
The invention disclosed herein overcomes these and other defects of the prior art technologies relating to division systems and contributes a remarkable improvement of the structure and performance of the division system.